#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/9/11 14:30
# @Author  : Yuyun
# @File    : 递归遍历.py
# @IDE     : PyCharm
class TreeNode:
    def __init__(self, val, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    """
    前序遍历：中-左-右
    """
    def preorder_traversal(self, root:TreeNode):
        res = []
        def dfs(node):
            if node is None:
                return
            res.append(node.val)
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return res
    """
    中序遍历：左-中-右
    """
    def midorder_traversal(self, root:TreeNode):
        res = []
        def dfs(node):
            if node is None:
                return
            dfs(node.left)
            res.append(node.val)
            dfs(node.right)
        dfs(root)
        return res

    #   更直接的写法
    def midorder_traversal_I(self, root: TreeNode, res=None):
        if res is None:
            res = []
        if root:
            res = self.midorder_traversal_I(root.left, res)
            res.append(root.val)
            res = self.midorder_traversal_I(root.right, res)
        return res

    """
    后序遍历：左-右-中
    """
    def postorder_traveral(self, root:TreeNode):
        res = []
        def dfs(node):
            if node is None:
                return
            dfs(node.left)
            dfs(node.right)
            res.append(node.val)
        dfs(root)
        return res
    """
    层序遍历：BFS
    """
    def levelorder_traversal(self, root:TreeNode):
        if root is None:
            return
        res = []
        def bfs(node):
            bfs(node.left)
            bfs(node.right)
            res.append(node.val)

        bfs(root)
        return res